/**
*		@file QueryEvaulator.cpp
*		@brief QueryEvaulator class
*
*		@author Lan Ziquan
*       @author KLM
*		@date 02/11/2012
*/
#include "QueryEvaulator.h"
#include "Compare.h"
#include "AbstractWrapper.h"
using namespace std;


struct ThreadResult{
	QueryThread* p_query_thread;
	ResultTable* p_result_table;
};
static bool g_query_thread_stop = false;

static vector<ThreadResult*> g_vp_thread_result;

static bool ClearGlobalVaribles()
{
	bool b_return = g_query_thread_stop;
	g_query_thread_stop = false;
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
	{
		if( g_vp_thread_result[i]->p_result_table != NULL )
			delete g_vp_thread_result[i]->p_result_table;
	}
	g_vp_thread_result.clear();
	return b_return;
}

static int GetSizeFromArgumentValue(vector<int>& known_sizes, QueryArgumentValue argument)
{
	if( argument <= 0 )
		return 1;
	if( known_sizes[argument - 1] > 0 )
		return known_sizes[argument - 1];
	switch( QueryVarTable::GetQueryVarType(argument) )
	{
	case PROC_TYPE:
		return ProcTable::GetSize();
	case VAR_TYPE:
		return VarTable::GetSize();
	case CONST_TYPE:
		return ConstTable::GetSize();
	case ASSIGN_TYPE:
		return StmtTable::GetSizeAssign();
	case WHILE_TYPE:
		return StmtTable::GetSizeWhile();
	case IF_TYPE:
		return StmtTable::GetSizeIf();
	case CALL_TYPE:
		return StmtTable::GetSizeCall();
	case STMT_TYPE:
		return StmtTable::GetSize();
	default:
		return 1;	//shoud not be here
	}
}

static QueryTNode* GetNextQuery(ResultTable* p_result_table, vector<QueryTNode*>& vp_query_tnodes)
{
	vector<int> known_sizes(QueryVarTable::GetSize(), 0);
	/*for( int i = 0; p_result_table != NULL && i < p_result_table->get_query_var_idxes()->size(); i++ )
	{
		vector<int> v_project_on;
		v_project_on.push_back(i);
		known_sizes[p_result_table->get_query_var_idxes()->at(i) - 1] =	
			p_result_table->ProjectOnCols(v_project_on, ! p_result_table->IsColumnSorted(v_project_on))->get_table_data()->size();
	}*/

	QueryTNode* result = NULL;
	for( vector<QueryTNode*>::iterator iter_p_query_tnode = vp_query_tnodes.begin();
		iter_p_query_tnode != vp_query_tnodes.end();
		iter_p_query_tnode++ )
	{
		
		if( (*iter_p_query_tnode)->priority < 0 )
			continue;
		QueryPriority current_priority = 1;
		switch( (*iter_p_query_tnode)->q_type ){
		case NEXT_ADV:
			current_priority *= ( (StmtTable::GetSizeWhile() + StmtTable::GetSizeIf() ) / 2 );
			break;
		case NEXTBIP_ADV:
			current_priority *= ( StmtTable::GetSizeCall() * (StmtTable::GetSizeWhile() + StmtTable::GetSizeIf() ) / 2 );
			break;
		case PATTERN_Q:
			switch( QueryVarTable::GetQueryVarType((*iter_p_query_tnode)->argument_a) )
			{
			case ASSIGN_TYPE:
				if( (*iter_p_query_tnode)->pattern == NULL || (*iter_p_query_tnode)->isRelaxed == false )
				{
					current_priority *= StmtTable::GetSizeAssign();
				}
				else
				{
					current_priority *= StmtTable::GetSizeAssign() * 4; // heuristic
				}
				break;
			default:
				current_priority *= 1; // case of IF_TYPE and WHILE_TYPE
			}
			break;
		case AFFECTS:
		case AFFECTSBIP:
			if( (*iter_p_query_tnode)->argument_a == 0 )
				current_priority *= StmtTable::GetSizeAssign() / 2;
			if( (*iter_p_query_tnode)->argument_b == 0 )
				current_priority *= StmtTable::GetSizeAssign() / 2;
			break;
		case AFFECTS_ADV:
			current_priority *= ( StmtTable::GetSizeAssign() * StmtTable::GetSizeAssign() / 2 );
			break;
		case AFFECTSBIP_ADV:
			current_priority *= StmtTable::GetSizeAssign() * StmtTable::GetSizeAssign();
			for( int i = 0; i < StmtTable::GetSizeWhile(); i++ )
				current_priority *= 2;
			break;
		default:
			current_priority *= 1;
		}

		current_priority *= GetSizeFromArgumentValue( known_sizes, (*iter_p_query_tnode)->argument_a );
		if( (*iter_p_query_tnode)->argument_a != (*iter_p_query_tnode)->argument_b )
			current_priority *= GetSizeFromArgumentValue( known_sizes, (*iter_p_query_tnode)->argument_b );
		
		(*iter_p_query_tnode)->priority = current_priority;

		if( result == NULL || result->priority > (*iter_p_query_tnode)->priority )
		{
			result = (*iter_p_query_tnode);
		}
	}
	if( result != NULL )
		result->priority = -1;
	return result;
}

static bool EvalQueryBool(
	QueryArgumentValue argument_a,
	QueryArgumentValue argument_b,
	QueryTNode query_tnode);

bool (*func_lst_bool[100])(int,int);

static void FunctionList(){
	func_lst_bool[FOLLOWS] = &Follows::IsFollows;
	func_lst_bool[FOLLOWS_ADV] = &Follows::IsFollowsAdv;
	func_lst_bool[PARENT] = &Parent::IsParent;
	func_lst_bool[PARENT_ADV] = &Parent::IsParentAdv;
	func_lst_bool[CALLS] = &Calls::IsCalls;
	func_lst_bool[CALLS_ADV] = &Calls::IsCallsAdv;
	func_lst_bool[NEXT] = &Next::IsNext;
	func_lst_bool[NEXT_ADV] = &Next::IsNextAdv;
	func_lst_bool[AFFECTS] = &Affects::IsAffects;
	func_lst_bool[AFFECTS_ADV] = &Affects::IsAffectsAdv;
	func_lst_bool[MODIFIES] = &Modifies::IsModifiesP;
	func_lst_bool[MODIFIES+10] = &Modifies::IsModifiesS;
	func_lst_bool[USES] = &Uses::IsUsesP;
	func_lst_bool[USES+10] = &Uses::IsUsesS;
	func_lst_bool[COMPARE] = &Compare::CompareValue;
	func_lst_bool[COMPARE+20] = &Compare::CompareNamePV;
	func_lst_bool[COMPARE+21] = &Compare::CompareNameVP;
	func_lst_bool[NEXTBIP] = &NextBip::IsNextBip;
	func_lst_bool[NEXTBIP_ADV] = &NextBip::IsNextBipAdv;
	func_lst_bool[AFFECTSBIP] = &AffectsBip::IsAffectsBip;
	func_lst_bool[AFFECTSBIP_ADV] = &AffectsBip::IsAffectsBipAdv;
	
}


bool EvalQueryBool(int val_a, int val_b, QueryTNode* query_tnode){
	if(query_tnode->q_type == MODIFIES || query_tnode->q_type == USES){
		if( (query_tnode->argument_a != 0 ) &&
			((val_a < 0 && query_tnode->special_type == STMT_TYPE) || 
			(val_a > 0 &&  QueryVarTable::GetQueryVarType(query_tnode->argument_a) != PROC_TYPE)) ) //may be dangerous
			return func_lst_bool[query_tnode->q_type+10](abs(val_a),abs(val_b));
	}
	return func_lst_bool[query_tnode->q_type](abs(val_a),abs(val_b));
}

static bool SingleEvaluation(QueryTNode* query_tnode, ResultTable* pre_result, ResultTable* post_result){

	FunctionList();
	QueryType query_type = query_tnode->q_type;
	QueryArgumentValue arg_a = query_tnode->argument_a;
	QueryArgumentValue arg_b = query_tnode->argument_b;
	TNodeType special_type = query_tnode->special_type;
	TNode* right_pattern = query_tnode->pattern;

	// FOLLOWS(*),PARENT(*),CALL(*),USES,MODIFIES
	if(query_type == FOLLOWS||query_type ==FOLLOWS_ADV
		||query_type ==PARENT||query_type ==PARENT_ADV
		||query_type ==CALLS||query_type ==CALLS_ADV
		||query_type ==NEXT||query_type ==NEXT_ADV
		||query_type ==AFFECTS||query_type ==AFFECTS_ADV
		||query_type ==MODIFIES||query_type ==USES
		||query_type ==NEXTBIP||query_type ==NEXTBIP_ADV
		||query_type ==AFFECTSBIP||query_type ==AFFECTSBIP_ADV){
		// both arguments are constant
		if(arg_a < 0 && arg_b <0) return EvalQueryBool(arg_a,arg_b,query_tnode);

		// left is underscore, right is constant
		if(arg_a == 0 && arg_b < 0) return EvalQueryBool(0,arg_b,query_tnode);

		// left is constant, right is underscore
		if(arg_a < 0 && arg_b ==0 ) return EvalQueryBool(arg_a,0,query_tnode);

		// both arguments are underscore
		if (arg_a == 0 && arg_b == 0) return EvalQueryBool(0,0,query_tnode);

		// 1 argument is constant, 1 argument is unknown
		bool result_bool = false;
		for(int i =0; i<(*pre_result->get_table_data()).size(); i++)
		{
			if(arg_a<0 && arg_b>0) result_bool = EvalQueryBool(arg_a, (*pre_result->get_table_data())[i][0], query_tnode);
			else if(arg_a>0 && arg_b<0) result_bool = EvalQueryBool((*pre_result->get_table_data())[i][0], arg_b, query_tnode);
			else if(arg_a>0&&arg_b==0) result_bool = EvalQueryBool((*pre_result->get_table_data())[i][0], 0, query_tnode);
			else if(arg_a==0&&arg_b>0) result_bool = EvalQueryBool(0, (*pre_result->get_table_data())[i][0], query_tnode);
			else if(arg_a == arg_b) result_bool = EvalQueryBool((*pre_result->get_table_data())[i][0],(*pre_result->get_table_data())[i][0] , query_tnode);
			else result_bool = EvalQueryBool((*pre_result->get_table_data())[i][0], (*pre_result->get_table_data())[i][1], query_tnode);

			if(result_bool) post_result->get_table_data()->push_back((*pre_result->get_table_data())[i]);
		}
	}

	//PATTERN query:
	//condition1: a(_,pattern)
	//condition2: a("",pattern)
	//condition3: a(v,pattern)
	else if(query_type==PATTERN_Q){
		bool result_bool = false;
		for(int i=0;i<(*pre_result->get_table_data()).size();i++)
		{
			TNode* pattern = StmtTable::GetStmtTNode((*pre_result->get_table_data())[i][0]);
			if(arg_b == 0) result_bool = AST::IsPatternMatch(pattern, 0, right_pattern, query_tnode->isRelaxed);
			else if(arg_b<=0) result_bool = AST::IsPatternMatch(pattern, abs(arg_b), right_pattern, query_tnode->isRelaxed);
			else result_bool = AST::IsPatternMatch(pattern, (*pre_result->get_table_data())[i][1], right_pattern, query_tnode->isRelaxed);
			if(result_bool) (*post_result->get_table_data()).push_back((*pre_result->get_table_data())[i]);
		}
	}

	//COMPARE query:
	//condition1: left variable, right constant
	//            p.procName = ""
	//            c.procName = ""
	//condition2: left constant, right constant
	//            stmt# = stmt#
	//            cp,cv,cc/pp,pv,pc/vp,vv,vc 
	else if(query_type == COMPARE){
		bool result_bool = false;
		for(int i = 0; i<(*pre_result->get_table_data()).size();i++)
		{
			int val_a = (*pre_result->get_table_data())[i][0];
			int val_b = 0;

			//condition1
			if(arg_a > 0 && arg_b <= 0) {
				if(QueryVarTable::GetQueryVarType(abs(arg_a))==CALL_TYPE){
					if(special_type==PROC_TYPE) result_bool = func_lst_bool[query_type](StmtTable::GetStmtTNode(val_a)->value,abs(arg_b)); //c.procName
					else result_bool = func_lst_bool[query_type](val_a,abs(arg_b)); //#
				}else result_bool = func_lst_bool[query_type](val_a,abs(arg_b));
			}

			//condition2
			else{
				if(arg_a == arg_b) val_b = val_a;
				else val_b = (*pre_result->get_table_data())[i][1];

				switch(QueryVarTable::GetQueryVarType(abs(arg_a))){
				case STMT_TYPE: case IF_TYPE: case WHILE_TYPE: case ASSIGN_TYPE: case CONST_TYPE:
					result_bool = func_lst_bool[query_type](val_a,val_b);
					break;
				case CALL_TYPE: 
					if(special_type==STMT_TYPE) {                     //c.stmt#
						result_bool = func_lst_bool[query_type](val_a,val_b);
						break;
					}
					else val_a = StmtTable::GetStmtTNode(val_a)->value; //c.procName
					// no break, to compare cp,cv,cc
				case PROC_TYPE:  //pp,pv,pc
					switch(QueryVarTable::GetQueryVarType(abs(arg_b))){
					case PROC_TYPE:
						result_bool = func_lst_bool[query_type](val_a,val_b);
						break;
					case VAR_TYPE:
						result_bool = func_lst_bool[query_type+20](val_a,val_b);
						break;
					case CALL_TYPE:
						result_bool = func_lst_bool[query_type](val_a,StmtTable::GetStmtTNode(val_b)->value);
						break;
					default: // should not be here
						cout<<"WRONG TYPE"<<endl;
						break;
					}
					break;
				case VAR_TYPE:  //vp,vv,vc
					switch(QueryVarTable::GetQueryVarType(abs(arg_b))){
					case PROC_TYPE: 
						result_bool = func_lst_bool[query_type+21](val_a,val_b);
						break;
					case VAR_TYPE:
						result_bool = func_lst_bool[query_type](val_a,val_b);
						break;
					case CALL_TYPE:
						result_bool = func_lst_bool[query_type+21](val_a,StmtTable::GetStmtTNode(val_b)->value);
						break;
					default: // should not be here
						cout<<"WRONG TYPE"<<endl;
						break;
					}
					break;
				default: // should not be here
					cout<<"WRONG TYPE"<<endl;
					break;	
				}
			}
			if(result_bool) (*post_result->get_table_data()).push_back((*pre_result->get_table_data())[i]);
		}
	}

	if(post_result->get_table_data()->empty()) return false;
	else return true;
}

bool BooleanEvaluation()
{
	for( vector<QueryTNode*>::iterator iter_p_query_tnode = QueryTree::get_vp_query_tnodes()->begin();
		iter_p_query_tnode != QueryTree::get_vp_query_tnodes()->end();
		iter_p_query_tnode++)
	{
		if( (*iter_p_query_tnode)->q_type == STOP || AbstractWrapper::GlobalStop )
			return false;
		// case of query(const, const), query(const, _), quesry(_,const), query(_,_)
		if( (*iter_p_query_tnode)->argument_a <= 0 && (*iter_p_query_tnode)->argument_b <= 0 )
		{
			if( !SingleEvaluation( *iter_p_query_tnode, NULL, NULL ) ){	return false; }
		}
		else
			return true;
	}
	return true;
}

void NonBoolEvaluation(int thread_num)
{
	ResultTable* p_result_table_result = NULL;

	QueryTNode* p_query_tnode_current;
	while( (p_query_tnode_current = GetNextQuery(p_result_table_result, QueryTree::get_p_query_matrix()->at(thread_num))) != NULL )
	//for( vector<QueryTNode*>::iterator iter_p_query_tnode = QueryTree::get_p_query_matrix()->at(thread_num).begin();
	//	iter_p_query_tnode != QueryTree::get_p_query_matrix()->at(thread_num).end();
	//	iter_p_query_tnode++)
	{
		if( g_query_thread_stop || AbstractWrapper::GlobalStop )
		{
			g_query_thread_stop = true;
			return;
		}
		// case of query(qvar, const) and query(qvar, _)
		if( p_query_tnode_current->argument_a > 0
			&& p_query_tnode_current->argument_b <= 0 )
		{
			if( p_result_table_result == NULL )
			{
				ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_a, true);
				ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a);

				if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
				{
					delete p_result_table_pre;
					delete p_result_table_post;
					g_query_thread_stop = true;
					return;
				}
				p_result_table_result = p_result_table_post;
				delete p_result_table_pre;
				continue;
			}
			else
			{
				ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a);
				vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
				p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
				// have no common cols
				if( v_comm_cols_a.empty() )
				{
					ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_a, true);
					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
				// have some comm cols
				else
				{
					bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
					ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
			}
		}
		// case of query(const, qvar) and query(_,qvar)
		else if( p_query_tnode_current->argument_a <= 0
			&& p_query_tnode_current->argument_b > 0 )
		{
			if( p_result_table_result == NULL )
			{
				ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_b, true);
				ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_b);

				if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
				{
					delete p_result_table_pre;
					delete p_result_table_post;
					g_query_thread_stop = true;
					return;
				}
				p_result_table_result = p_result_table_post;
				delete p_result_table_pre;
				continue;
			}
			else
			{
				ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_b);
				vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
				p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
				// have no common cols
				if( v_comm_cols_a.empty() )
				{
					ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_b, true);
					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
				// have some comm cols
				else
				{
					bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
					ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
			}
		}
		// case of query(qvar, qvar)
		else if( p_query_tnode_current->argument_a > 0
			&& p_query_tnode_current->argument_b > 0 )
		{
			// case of argument_a is the same as argument_b
			if( p_query_tnode_current->argument_a == p_query_tnode_current->argument_b )
			{
				if( p_result_table_result == NULL )
				{
					ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_a, true);
					ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a);

					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_post;
					delete p_result_table_pre;
					continue;
				}
				else
				{
					ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a);
					vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
					p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					// have no common cols
					if( v_comm_cols_a.empty() )
					{
						ResultTable* p_result_table_pre = new ResultTable(p_query_tnode_current->argument_a, true);
						if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							g_query_thread_stop = true;
							return;
						}
						p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have some comm cols
					else
					{
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
						if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							g_query_thread_stop = true;
							return;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
				}
			}
			// case of argument_a is different from argument_b 
			else
			{
				if( p_result_table_result == NULL )
				{
					ResultTable* p_result_table_pre_a = new ResultTable(p_query_tnode_current->argument_a, true);
					ResultTable* p_result_table_pre_b = new ResultTable(p_query_tnode_current->argument_b, true);
					ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, true);
					delete p_result_table_pre_a;
					delete p_result_table_pre_b;
					ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a, p_query_tnode_current->argument_b);

					if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						g_query_thread_stop = true;
						return;
					}
					p_result_table_result = p_result_table_post;
					delete p_result_table_pre;
					continue;
				}
				else
				{
					ResultTable* p_result_table_post = new ResultTable(p_query_tnode_current->argument_a, p_query_tnode_current->argument_b);
					vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
					p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					// have no common cols
					if( v_comm_cols_a.empty() )
					{
						ResultTable* p_result_table_pre_a = new ResultTable(p_query_tnode_current->argument_a, true);
						ResultTable* p_result_table_pre_b = new ResultTable(p_query_tnode_current->argument_b, true);
						ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, true);
						delete p_result_table_pre_a;
						delete p_result_table_pre_b;
						if( !SingleEvaluation(p_query_tnode_current, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							g_query_thread_stop = true;
							return;
						}
						p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have 2 comm cols
					else if( v_comm_cols_a.size() == 2 )
					{
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
						if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							g_query_thread_stop = true;
							return;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have 1 comm col
					else
					{
						bool b_left_comm =  (v_comm_cols_b[0] == 0);
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre_a =
							( b_left_comm ?
							p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort) :
						new ResultTable(p_query_tnode_current->argument_a, true) );
						ResultTable* p_result_table_pre_b =
							( b_left_comm ?
							new ResultTable(p_query_tnode_current->argument_b, true) :
						p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort) );
						ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, b_left_comm);
						delete p_result_table_pre_a;
						delete p_result_table_pre_b;

						if( !SingleEvaluation( p_query_tnode_current, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							g_query_thread_stop = true;
							return;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
				}
			}
		}
	}
	// upto here, this thread result IS NEITHER false NOR none
	g_vp_thread_result[thread_num]->p_result_table = p_result_table_result;
	return;
}

// return cases:	true	non-empty result table	=>	tuple results
//					false	empty result table		=>	none
//					true	NULL result table		=>	true
//					false	NULL result table		=>	false

bool QueryEvaluation(ResultTable** pp_result_table)
{
	QueryThread::InitLock();
	// eval bool query
	if( !BooleanEvaluation() )
	{
		QueryThread::DeleteLock();
		ClearGlobalVaribles();
		// case of select BOOLEAN
		if( QueryTree::get_pv_result_tuple()->empty() )
		{
			*pp_result_table = NULL;
			return false;
		}
		// case of select NON BOOLEAN
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		return false;
	}
	
	for( int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++ )
	{
		ThreadResult* p_thread_result = new ThreadResult;
		p_thread_result->p_query_thread = new QueryThread();
		p_thread_result->p_result_table = NULL;
		g_vp_thread_result.push_back(p_thread_result);
	}
	// start all threads
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
		g_vp_thread_result[i]->p_query_thread->Start();
	// wait to join all threads
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
		g_vp_thread_result[i]->p_query_thread->Join();
	// delete all threads
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
		delete g_vp_thread_result[i]->p_query_thread;
	// delete lock
	QueryThread::DeleteLock();

	// merge all thread results
	// case 1	select BOOLEAN
	if( QueryTree::get_pv_result_tuple()->empty() )
	{
		*pp_result_table = NULL;
		return !ClearGlobalVaribles();
	}
	// case 2	select some query variables
	// case 2.1 answer is none
	if( g_query_thread_stop )
	{
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		ClearGlobalVaribles();
		return false;
	}
	// case 2.2	answer is not none
	// step 1. construct all merged result tables
	vector<ResultTable*> vp_merged_result_table;
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
	{
		if( i < g_vp_thread_result.size() - 1 )
		{
			vector<int> comm_cols_a, comm_cols_b, diff_cols_b;
			g_vp_thread_result[i]->p_result_table->FindCommAttri(
				g_vp_thread_result[i+1]->p_result_table,
				comm_cols_a, comm_cols_b, diff_cols_b);
			// case of has common cols
			if( !comm_cols_a.empty() )
			{
				vp_merged_result_table.push_back(
					g_vp_thread_result[i]->p_result_table->SortMergeJoin(
					g_vp_thread_result[i+1]->p_result_table, 
					comm_cols_a, comm_cols_b, diff_cols_b));
				i++;
				continue;
			}
		}
		vp_merged_result_table.push_back(g_vp_thread_result[i]->p_result_table);
	}
	// step 2. indicate the occurances of each selected variable in each merged result table
	vector<vector<int>> vv_occurance_idx_in_merged_table;	// w.r.t. vp_merged_result_table
	vv_occurance_idx_in_merged_table.resize( vp_merged_result_table.size() );
	vector<int>			v_no_occurance_idx_in_selection;	// w.r.t. QueryTree::get_pv_result_tuple()
	for( int i = 0; i < QueryTree::get_pv_result_tuple()->size(); i++ )	// for each selection entry
	{
		bool b_find_occurance = false;
		for( int j = 0; j < vp_merged_result_table.size(); j++ )	// for each merged table
		{
			for( int k = 0; k < vp_merged_result_table[j]->get_query_var_idxes()->size(); k++ ) // for each merged table schema entry
			{
				if( QueryTree::get_pv_result_tuple()->at(i) == vp_merged_result_table[j]->get_query_var_idxes()->at(k) )
				{
					vv_occurance_idx_in_merged_table[j].push_back(k);
					b_find_occurance = true;
					break;
				}
			}
			if( b_find_occurance )
				break;
		}
		if( !b_find_occurance )
			v_no_occurance_idx_in_selection.push_back(QueryTree::get_pv_result_tuple()->at(i));
	}
	// step 3. project on occurance cols
	vector<ResultTable*> vp_result_table_projected;
	for( int i = 0; i < vv_occurance_idx_in_merged_table.size(); i++ )
	{
		bool b_need_sort = vp_merged_result_table[i]->IsColumnSorted(vv_occurance_idx_in_merged_table[i]);
		vp_result_table_projected.push_back(
			vp_merged_result_table[i]->ProjectOnCols(vv_occurance_idx_in_merged_table[i], !b_need_sort));
	}
	// step 4. add non occurance cols into projected
	for( int i = 0; i < v_no_occurance_idx_in_selection.size(); i++ )
		vp_result_table_projected.push_back(new ResultTable(v_no_occurance_idx_in_selection[i],true));
	// step 5. integrate all together
	ResultTable* p_result_table_integrated = NULL;
	for( int i = 0; i < vp_result_table_projected.size(); i++ )
	{
		if( p_result_table_integrated == NULL )
		{
			p_result_table_integrated = vp_result_table_projected[i];
			continue;
		}	
		p_result_table_integrated = p_result_table_integrated->CartesianProduct(vp_result_table_projected[i],true);
	}
	// step 6.1 empty table
	if( p_result_table_integrated->get_table_data()->empty() )
	{
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		ClearGlobalVaribles();
		return false;
	}
	// step 6.2 sort cols of integrated table to get the final result table
	*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
	vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
	p_result_table_integrated->FindCommAttri( (*pp_result_table), v_comm_cols_a, v_comm_cols_b, v_diff_cols_b );
	*pp_result_table = p_result_table_integrated->ProjectOnCols( v_comm_cols_a, false );
	ClearGlobalVaribles();
	return true;
}


// return cases:	true	non-empty result table	=>	tuple results
//					false	empty result table		=>	none
//					true	NULL result table		=>	true
//					false	NULL result table		=>	false

bool BQE(ResultTable** pp_result_table){
	
	QueryThread::InitLock();
	// eval bool query
	if( !BooleanEvaluation() )
	{
		QueryThread::DeleteLock();
		ClearGlobalVaribles();
		// case of select BOOLEAN
		if( QueryTree::get_pv_result_tuple()->empty() )
		{
			*pp_result_table = NULL;
			return false;
		}
		// case of select NON BOOLEAN
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		return false;
	}
	
	for( int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++ )
	{
		ThreadResult* p_thread_result = new ThreadResult;
		p_thread_result->p_query_thread = NULL;
		p_thread_result->p_result_table = NULL;
		g_vp_thread_result.push_back(p_thread_result);
	}
	for( int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++ )
	{
		NonBoolEvaluation(i);
	}
	QueryThread::DeleteLock();

	// merge all thread results
	// case 1	select BOOLEAN
	if( QueryTree::get_pv_result_tuple()->empty() )
	{
		*pp_result_table = NULL;
		return !ClearGlobalVaribles();
	}
	// case 2	select some query variables
	// case 2.1 answer is none
	if( g_query_thread_stop )
	{
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		ClearGlobalVaribles();
		return false;
	}
	// case 2.2	answer is not none
	// step 1. construct all merged result tables
	vector<ResultTable*> vp_merged_result_table;
	for( int i = 0; i < g_vp_thread_result.size(); i++ )
	{
		if( i < g_vp_thread_result.size() - 1 )
		{
			vector<int> comm_cols_a, comm_cols_b, diff_cols_b;
			g_vp_thread_result[i]->p_result_table->FindCommAttri(
				g_vp_thread_result[i+1]->p_result_table,
				comm_cols_a, comm_cols_b, diff_cols_b);
			// case of has common cols
			if( !comm_cols_a.empty() )
			{
				vp_merged_result_table.push_back(
					g_vp_thread_result[i]->p_result_table->SortMergeJoin(
					g_vp_thread_result[i+1]->p_result_table, 
					comm_cols_a, comm_cols_b, diff_cols_b));
				i++;
				continue;
			}
		}
		vp_merged_result_table.push_back(g_vp_thread_result[i]->p_result_table);
	}
	// step 2. indicate the occurances of each selected variable in each merged result table
	vector<vector<int>> vv_occurance_idx_in_merged_table;	// w.r.t. vp_merged_result_table
	vv_occurance_idx_in_merged_table.resize( vp_merged_result_table.size() );
	vector<int>			v_no_occurance_idx_in_selection;	// w.r.t. QueryTree::get_pv_result_tuple()
	for( int i = 0; i < QueryTree::get_pv_result_tuple()->size(); i++ )	// for each selection entry
	{
		bool b_find_occurance = false;
		for( int j = 0; j < vp_merged_result_table.size(); j++ )	// for each merged table
		{
			for( int k = 0; k < vp_merged_result_table[j]->get_query_var_idxes()->size(); k++ ) // for each merged table schema entry
			{
				if( QueryTree::get_pv_result_tuple()->at(i) == vp_merged_result_table[j]->get_query_var_idxes()->at(k) )
				{
					vv_occurance_idx_in_merged_table[j].push_back(k);
					b_find_occurance = true;
					break;
				}
			}
			if( b_find_occurance )
				break;
		}
		if( !b_find_occurance )
			v_no_occurance_idx_in_selection.push_back(QueryTree::get_pv_result_tuple()->at(i));
	}
	// step 3. project on occurance cols
	vector<ResultTable*> vp_result_table_projected;
	for( int i = 0; i < vv_occurance_idx_in_merged_table.size(); i++ )
	{
		bool b_need_sort = vp_merged_result_table[i]->IsColumnSorted(vv_occurance_idx_in_merged_table[i]);
		vp_result_table_projected.push_back(
			vp_merged_result_table[i]->ProjectOnCols(vv_occurance_idx_in_merged_table[i], !b_need_sort));
	}
	// step 4. add non occurance cols into projected
	for( int i = 0; i < v_no_occurance_idx_in_selection.size(); i++ )
		vp_result_table_projected.push_back(new ResultTable(v_no_occurance_idx_in_selection[i],true));
	// step 5. integrate all together
	ResultTable* p_result_table_integrated = NULL;
	for( int i = 0; i < vp_result_table_projected.size(); i++ )
	{
		if( p_result_table_integrated == NULL )
		{
			p_result_table_integrated = vp_result_table_projected[i];
			continue;
		}	
		p_result_table_integrated = p_result_table_integrated->CartesianProduct(vp_result_table_projected[i],true);
	}
	// step 6.1 empty table
	if( p_result_table_integrated->get_table_data()->empty() )
	{
		*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
		ClearGlobalVaribles();
		return false;
	}
	// step 6.2 sort cols of integrated table to get the final result table
	*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );
	vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
	p_result_table_integrated->FindCommAttri( (*pp_result_table), v_comm_cols_a, v_comm_cols_b, v_diff_cols_b );
	*pp_result_table = p_result_table_integrated->ProjectOnCols( v_comm_cols_a, false );
	ClearGlobalVaribles();
	return true;
}

/*
bool BQE(ResultTable** pp_result_table){
	bool b_none_or_false = false;
	ResultTable* p_result_table_result = NULL;

	vector<QueryTNode*>::iterator iter_p_query_tnode;

	// YUCHEN added:
	int query_count = 0; 
	// YUCHEN added: 
	for( iter_p_query_tnode = QueryTree::get_vp_query_tnodes()->begin();
		iter_p_query_tnode != QueryTree::get_vp_query_tnodes()->end();
		iter_p_query_tnode++)
	{
		// YUCHEN added:
		cout << "start query node:" << query_count << endl;
		cout << "size of result table: ";
		if(p_result_table_result != NULL) cout << p_result_table_result->get_table_data()->size() << endl;
		else cout << "0" << endl;
		query_count++;
		// YUCHEN added:

		if( (*iter_p_query_tnode)->q_type == STOP )
		{
			b_none_or_false = true;
			p_result_table_result = NULL;
			break;
		}
		// case of query(const, const), query(const, _), quesry(_,const), query(_,_)
		if( (*iter_p_query_tnode)->argument_a <= 0
			&& (*iter_p_query_tnode)->argument_b <= 0 )
		{
			if( !SingleEvaluation( *iter_p_query_tnode, NULL, NULL ) )
			{
				b_none_or_false = true;
				p_result_table_result = NULL;
				break;
			}
			continue;
		}
		// case of query(qvar, const) and query(qvar, _)
		else if( (*iter_p_query_tnode)->argument_a > 0
			&& (*iter_p_query_tnode)->argument_b <= 0 )
		{
			if( p_result_table_result == NULL )
			{
				ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_a, true);
				ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a);

				if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
				{
					delete p_result_table_pre;
					delete p_result_table_post;
					b_none_or_false = true;
					p_result_table_result = NULL;
					break;
				}
				p_result_table_result = p_result_table_post;
				delete p_result_table_pre;
				continue;
			}
			else
			{
				ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a);
				vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
				p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
				// have no common cols
				if( v_comm_cols_a.empty() )
				{
					ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_a, true);
					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
				// have some comm cols
				else
				{
					bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
					ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
			}
		}
		// case of query(const, qvar) and query(_,qvar)
		else if( (*iter_p_query_tnode)->argument_a <= 0
			&& (*iter_p_query_tnode)->argument_b > 0 )
		{
			if( p_result_table_result == NULL )
			{
				ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_b, true);
				ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_b);

				if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
				{
					delete p_result_table_pre;
					delete p_result_table_post;
					b_none_or_false = true;
					p_result_table_result = NULL;
					break;
				}
				p_result_table_result = p_result_table_post;
				delete p_result_table_pre;
				continue;
			}
			else
			{
				ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_b);
				vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
				p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
				// have no common cols
				if( v_comm_cols_a.empty() )
				{
					ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_b, true);
					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
				// have some comm cols
				else
				{
					bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
					ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					delete p_result_table_pre;
					delete p_result_table_post;
					continue;
				}
			}
		}
		// case of query(qvar, qvar)
		else if( (*iter_p_query_tnode)->argument_a > 0
			&& (*iter_p_query_tnode)->argument_b > 0 )
		{
			// case of argument_a is the same as argument_b
			if( (*iter_p_query_tnode)->argument_a == (*iter_p_query_tnode)->argument_b )
			{
				if( p_result_table_result == NULL )
				{
					ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_a, true);
					ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a);

					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_post;
					delete p_result_table_pre;
					continue;
				}
				else
				{
					ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a);
					vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
					p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					// have no common cols
					if( v_comm_cols_a.empty() )
					{
						ResultTable* p_result_table_pre = new ResultTable((*iter_p_query_tnode)->argument_a, true);
						if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							b_none_or_false = true;
							p_result_table_result = NULL;
							break;
						}
						p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have some comm cols
					else
					{
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
						if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							b_none_or_false = true;
							p_result_table_result = NULL;
							break;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
				}
			}
			// case of argument_a is different from argument_b 
			else
			{
				if( p_result_table_result == NULL )
				{
					ResultTable* p_result_table_pre_a = new ResultTable((*iter_p_query_tnode)->argument_a, true);
					ResultTable* p_result_table_pre_b = new ResultTable((*iter_p_query_tnode)->argument_b, true);
					ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, true);
					delete p_result_table_pre_a;
					delete p_result_table_pre_b;
					ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a, (*iter_p_query_tnode)->argument_b);

					if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
					{
						delete p_result_table_pre;
						delete p_result_table_post;
						b_none_or_false = true;
						p_result_table_result = NULL;
						break;
					}
					p_result_table_result = p_result_table_post;
					delete p_result_table_pre;
					continue;
				}
				else
				{
					ResultTable* p_result_table_post = new ResultTable((*iter_p_query_tnode)->argument_a, (*iter_p_query_tnode)->argument_b);
					vector<int> v_comm_cols_a, v_comm_cols_b, v_diff_cols_b;
					p_result_table_result->FindCommAttri(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
					// have no common cols
					if( v_comm_cols_a.empty() )
					{
						ResultTable* p_result_table_pre_a = new ResultTable((*iter_p_query_tnode)->argument_a, true);
						ResultTable* p_result_table_pre_b = new ResultTable((*iter_p_query_tnode)->argument_b, true);
						ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, true);
						delete p_result_table_pre_a;
						delete p_result_table_pre_b;
						if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							b_none_or_false = true;
							p_result_table_result = NULL;
							break;
						}
						p_result_table_result = p_result_table_result->CartesianProduct(p_result_table_post,true);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have 2 comm cols
					else if( v_comm_cols_a.size() == 2 )
					{
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre = p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort);
						if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							b_none_or_false = true;
							p_result_table_result = NULL;
							break;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
					// have 1 comm col
					else
					{
						bool b_left_comm =  (v_comm_cols_b[0] == 0);
						bool b_need_sort = p_result_table_result->IsColumnSorted(v_comm_cols_a);
						ResultTable* p_result_table_pre_a =
							( b_left_comm ?
							p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort) :
						new ResultTable((*iter_p_query_tnode)->argument_a, true) );
						ResultTable* p_result_table_pre_b =
							( b_left_comm ?
							new ResultTable((*iter_p_query_tnode)->argument_b, true) :
						p_result_table_result->ProjectOnCols(v_comm_cols_a, !b_need_sort) );
						ResultTable* p_result_table_pre = p_result_table_pre_a->CartesianProduct(p_result_table_pre_b, b_left_comm);
						delete p_result_table_pre_a;
						delete p_result_table_pre_b;

						if( !SingleEvaluation( *iter_p_query_tnode, p_result_table_pre, p_result_table_post) )
						{
							delete p_result_table_pre;
							delete p_result_table_post;
							b_none_or_false = true;
							p_result_table_result = NULL;
							break;
						}
						p_result_table_result = p_result_table_result->SortMergeJoin(p_result_table_post, v_comm_cols_a, v_comm_cols_b, v_diff_cols_b);
						delete p_result_table_pre;
						delete p_result_table_post;
						continue;
					}
				}
			}
		}
	}
	// upto here, if b_none_or_false is true then the answer will be FALSE or NONE
	// otherwise, the answer will be TRUE or some result tuples

	// case 1	select BOOLEAN
	if( QueryTree::get_pv_result_tuple()->empty() )
	{
		*pp_result_table = NULL;
		return !b_none_or_false;
	}
	// case 2	select some query variables
	// case 2.1 answer is none
	if( b_none_or_false )
	{
		ResultTable* p_result_table_empty = new ResultTable( *(QueryTree::get_pv_result_tuple()));
		*pp_result_table = p_result_table_empty;
		return false;
	}
	// case 2.2	answer is not none
	// case 2.2.1	all clauses are not using any query variables
	if( p_result_table_result == NULL )
	{
		ResultTable* p_result_table_all_irrelevant = NULL;
		vector<QueryVarIdx>* p_v_qvar_idx_root_schema = QueryTree::get_pv_result_tuple();
		for( int i = 0; i < p_v_qvar_idx_root_schema->size(); i++ )
		{
			ResultTable* p_result_table_enum = new ResultTable(p_v_qvar_idx_root_schema->at(i), true);
			if( p_result_table_all_irrelevant == NULL )
				p_result_table_all_irrelevant = p_result_table_enum;
			else
				p_result_table_all_irrelevant = p_result_table_all_irrelevant->CartesianProduct(p_result_table_enum, true);
		}
		*pp_result_table = p_result_table_all_irrelevant;
		return true;
	}
	// case 2.2.2	some clauses are using some query variables
	*pp_result_table = new ResultTable( *(QueryTree::get_pv_result_tuple()) );

	vector<int> v_comm_cols_clauses, v_comm_cols_root, v_diff_cols_root;
	p_result_table_result->FindCommAttri((*pp_result_table), v_comm_cols_clauses, v_comm_cols_root, v_diff_cols_root);

	// construct all comm cols
	ResultTable* p_result_table_comm = NULL;
	if( !v_comm_cols_clauses.empty() )
	{
		p_result_table_comm = p_result_table_result->ProjectOnCols(v_comm_cols_clauses, !p_result_table_result->IsColumnSorted(v_comm_cols_clauses));
	}

	// construct enum of all diff cols
	ResultTable* p_result_table_diff = NULL;
	vector<QueryVarIdx>* p_v_qvar_idx_root_schema = QueryTree::get_pv_result_tuple();
	vector<int>::iterator iter_int_diff;
	for( iter_int_diff = v_diff_cols_root.begin();
		iter_int_diff != v_diff_cols_root.end();
		iter_int_diff++ )
	{
		ResultTable* p_result_table_enum = new ResultTable(p_v_qvar_idx_root_schema->at(*iter_int_diff), true);
		if( p_result_table_diff == NULL )
			p_result_table_diff = p_result_table_enum;
		else
			p_result_table_diff = p_result_table_diff->CartesianProduct(p_result_table_enum, true);
	}

	// construct all cols
	ResultTable* p_result_table_all = NULL;
	if( p_result_table_diff == NULL )
		p_result_table_all = p_result_table_comm;
	else if( p_result_table_comm == NULL )
		p_result_table_all = p_result_table_diff;
	else
	{
		p_result_table_all = p_result_table_comm->CartesianProduct(p_result_table_diff, true);
	}

	// sort cols
	v_comm_cols_root.clear();
	v_diff_cols_root.clear();
	vector<int> v_comm_cols_all;
	p_result_table_all->FindCommAttri((*pp_result_table), v_comm_cols_all, v_comm_cols_root, v_diff_cols_root);

	(*pp_result_table) = p_result_table_all->ProjectOnCols(v_comm_cols_all, !p_result_table_result->IsColumnSorted(v_comm_cols_all));
	return true;
}
*/